package Sort;


/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}20:36
 */
public class MergetSort {
    public static void main(String[] args) {
        int arr[] = {7,3,19,40,4,1};
        int temp[] = new int[arr.length];
        merget(arr, 0, arr.length - 1, temp);
        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }

    //先写治

    //第二步（分）
    public static void merget(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            merget(arr, left, mid, temp);
            merget(arr, mid + 1, right, temp);
            merget(arr, left, right, mid, temp);
        }
    }

    //第一步将分好的放入辅助数组中（治）
    public static void merget(int[] arr, int left, int right, int mid, int[] temp) {
        int l = left;
        int r = mid + 1;
        int index = 0;
        while (l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                temp[index++] = arr[l];
                l++;
            } else {
                temp[index++] = arr[r];
                r++;
            }

            while (l <= mid) {
                temp[index++] = arr[l];
                l++;
            }
            while (r <= right) {
                temp[index++] = arr[r];
                r++;
            }

            //之后是将排好的转移到原来的数组中
            index = 0;
            int leftIndex = left;
            while (leftIndex <= right) {
                arr[leftIndex] = temp[index];
                index++;
                leftIndex++;
            }
        }
    }
}
